package learn.sort;

import java.util.Arrays;

/**
 * @author 于昂
 * Date 2021/1/13
 * Time 19:50
 */
public class QuickSort {
    public static void main(String[] args) {
//        int[] array = {-9, 78, 0, 23, -567, 70};
//        int[] array = {100,78, 0, 23, 567, 70};
        int[] array = new int[80000];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 800000);
        }
        Long startTime = System.currentTimeMillis();
        quickSort(array, 0, array.length - 1);
        Long endTime = System.currentTimeMillis();
        long tempTime = (endTime - startTime);
        System.out.println("花费时间：" +
                (((tempTime / 86400000) > 0) ? ((tempTime / 86400000) + "d") : "") +
                ((((tempTime / 86400000) > 0) || ((tempTime % 86400000 / 3600000) > 0)) ? ((tempTime % 86400000 / 3600000) + "h") : ("")) +
                ((((tempTime / 3600000) > 0) || ((tempTime % 3600000 / 60000) > 0)) ? ((tempTime % 3600000 / 60000) + "m") : ("")) +
                ((((tempTime / 60000) > 0) || ((tempTime % 60000 / 1000) > 0)) ? ((tempTime % 60000 / 1000) + "s") : ("")) +
                ((tempTime % 1000) + "ms"));
//        System.out.println(Arrays.toString(array));
    }

    /**
     * @param array 排序的数组
     * @param left 左侧起点
     * @param right 右侧起点
     */
    public static void quickSort(int[] array, int left, int right) {
        int l = left; //获取循环变量，在下面的循环中会改变
        int r = right;
        int pivot = array[(l + r) / 2];//中间值
        //比pivot小的值，放到pivot左边 大的放到右边
        while (l < r) {
            while (array[l] < pivot) {//在pivot的左边，找到一个>=pivot的值 获取他的索引
                l++;
            }
            while (array[r] > pivot) {//在pivot的右边，找到一个<=pivot的值 获取他的索引
                r--;
            }
            if (l >= r) {//数组已经遍历完成，是有序的了
                //pivot左右两边的值 左边全部是<=pivot的值 右边全部是>=pivot的值
                break;
            } else {//找到左右两边不平衡的数了
                int temp = array[l];
                array[l] = array[r];
                array[r] = temp;
            }
            if (array[l] == pivot) {//右边的值一直找到了pivot本身的位置，pivot与array[l]进行了交换，此时r指向原来pivot的索引 这样会造成死循环，让r向左进一位，下面的l也是同理
                r--;
            }
            if (array[r] == pivot) {
                l++;
            }
        }
        if (l == r) {//上面的遍历没有交换值，l==r==中间的位置
            l++;
            r--;
        }
        if (left < r) {
            quickSort(array, left, r);
        }
        if (right > l) {
            quickSort(array, l, right);
        }
    }
}
